/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: list.c 53 2009-12-24 20:43:05Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <errno.h>
#include <string.h>
#include <stdio.h>

#include "list.h"
#include "function_prototypes.h"
#include "utilities.h"

/*******************************************************************************
 * Internal Declarartions.
 ******************************************************************************/
/* This is an internal helper that we are going to use to find an item in the
   list. We insert, remove and get using this same function. */
ListNode * list_get_helper (const List *list, size_t pos);

/* a helper function for the two list_create functions. Make a new list with
   the given type. */
List * list_create_helper (ListType type);

/*******************************************************************************
 * Library Definitions.
 ******************************************************************************/
void *
list_remove_helper (List *list, ListNode *cur)
{
  void *item;

  assert (list != NULL);
  assert (cur != NULL);

  item = (void *)cur->item;

  /* Link the prev and next nodes to each other, eliminating this node. */
  if (cur != list->head && cur != list->tail)
    {
      cur->next->prev = cur->prev;
      cur->prev->next = cur->next;
    }
  /* Removing the head or tail is slightly different for doubley linked 
     lists. */
  else if (list->type == DOUBLEY_LINKED)
    {
      /* These aren't elsed together because it's possible for it to be both
	 the head and the tail. Doing it this wat will clean up both. */

      /* Gotta do some clean up if pos was head. */
      if (cur == list->head)
	{
	  list->head = list->head->next;
	  if (list->head != NULL)
	    list->head->prev = NULL;
	}
      
      /* Gotta do some clean up if pos was tail. */
      if (cur == list->tail)
	{
	  list->tail = list->tail->prev;
	  if (list->tail != NULL)
	    list->tail->next = NULL;
	}
    }
  /* Removing the head or tail is slightly different for circular linked 
     lists. */
  else if (list->type == CIRCULAR_DOUBLEY_LINKED)
    {
      /* We can't do the same for a circular as above because the links to 
	 each other would get messed up. */

      /* This is the only element. */
      if (list->size == 1)
	{
	  list->head = NULL;
	  list->tail = NULL;
	}
      /* Link the new head to the tail. */
      else if (cur == list->head)
	{
	  list->head = list->head->next;
	  list->head->prev = list->tail;
	  list->tail->next = list->head;
	}
      /* Link the new tail to the head. */
      else if (cur == list->tail)
	{
	  list->tail = list->tail->prev;
	  list->tail->next = list->head;
	  list->head->prev = list->tail;
	}
    }
      
  free (cur);
  list->size--;

  return item;
}

int 
list_insert_helper (List *list, ListNode *node, const void *item, 
		    const int after)
{
  ListNode *new_node;

  assert (list != NULL);

  /* Make the new node. */
  new_node = malloc (sizeof (struct list_node));
  if (new_node == NULL)
    return 0;

  /* Start fresh. */
  new_node->prev = NULL;
  new_node->next = NULL;
  new_node->item = item;

  /* Decide where what our node is, if it's NULL. This could still result in
     NULL if the list is empty but the next block will catch it. */
  if (node == NULL && after == 1)
    node = list->tail;
  else if (node == NULL)
    node = list->head;

  /* We are the only item in the list. */
  if (list->size == 0) 
    {
      /* The first node is both the head and the tail. */
      list->head = new_node;
      list->tail = new_node;

      /* They need to link to each other if we are circular. */
      if (list->type == CIRCULAR_DOUBLEY_LINKED)
	{
	  new_node->next = new_node;
	  new_node->prev = new_node;
	}
    }
  /* Insert it inside the list. */
  else if (after)
    {
      /* Link node to it's neighbors. */
      new_node->prev = node;
      new_node->next = node->next;
      if (node->next != NULL)
	node->next->prev = new_node;
      node->next = new_node;

      /* We may need to update the tail. */
      if (node == list->tail)
	list->tail = new_node;
    }
  /* Insert it before. */
  else
    {
      /* Link node to it's neighbors. */
      new_node->next = node;
      new_node->prev = node->prev;
      if (node->prev != NULL)
	node->prev->next = new_node;
      node->prev = new_node;

      /* We may need to update the head. */
      if (node == list->head)
	list->head = new_node;
    }

  list->size++;

  return 1;
}

List * 
list_create ()
{
  return list_create_helper (DOUBLEY_LINKED);
}

List * 
list_create_circular ()
{
  return list_create_helper (CIRCULAR_DOUBLEY_LINKED);
}

List *
list_copy (const List *src, copy_func *cfunc,
	   destroy_func *dfunc)
{
  List *dest;          /* The new list. */
  ListTraverser trav;
  void *cur;           /* The current item in the main loop. */
  void *new_item;      /* The item to be inserted into the new list. */
  int tmp_errno;
  
  assert (src != NULL);
  assert ((cfunc != NULL ? dfunc != NULL : dfunc == NULL));
  
  /* Create the new list of the same type. */
  dest = list_create_helper (src->type);
  if (dest == NULL)
    return NULL;

  /* Loop through all of the items in the source list. */
  list_traverser_init (&trav, src);
  while ((cur = list_traverser_next (&trav)) != NULL)
    {
      /* Create the new memory or link to the old. */
      if (cfunc != NULL)
	new_item = cfunc (cur);
      else
	new_item = cur;

      /* If creation failed, we need to bail out. */
      if (new_item == NULL)
	break;

      /* If insertion failed, we need to bail out. */
      if (list_insert_last (dest, new_item) == 0)
	break;

      /* If we've inserted them all, we are done. */
      if (list_size (dest) == list_size (src))
	return dest;
    }

  /* Breaking out of the loop or ending it is a failure case. Clean up and
     return. */
  tmp_errno = errno;
  list_destroy (dest, dfunc);
  errno = tmp_errno;
  return NULL;
}

void
list_destroy (List *list, destroy_func *func)
{
  void *item;
  
  assert (list != NULL);

  /* Remove all the items from the list. */
  while (list_size (list) > 0)
    {
      item = list_remove_first (list);

      /* Use the destroyer func on each item if it's there. */
      if (func != NULL)
	(*func) ( (void *)item);
    }

  free (list);
}

void *
list_get (const List *list, const size_t pos)
{
  ListNode *cur;

  assert (list != NULL);

  /* Standard fail cases:
     1 - If there is nothing in the list, we can't get anything from it.
     2 - If the pos is larger than the list, we aren't going to find it.
     3 - If the pos is less than 0, it's not going to be in this list.
  */
  if (list_size (list) == 0 || pos >= list_size (list) || pos < 0)
    return NULL;

  /* User the helper to find the node. */
  cur = list_get_helper (list, pos);

  /* Return the item from the node. */
  return  (void *)cur->item;

}

void *
list_remove (List *list, const size_t pos)
{
  assert (list != NULL);

  /* Standard fail cases:
     1 - If there is nothing in the list, we can't remove anything from it.
     2 - If the pos is larger than the list, we won't find it in the list.
     3 - If the pos is less than 0, it's not going to be in this list.
  */
  if (list_size (list) == 0 || pos >= list_size (list) || pos < 0)
    return NULL;

  /* Use the helper to find and remove the node. */
  return list_remove_helper (list, list_get_helper (list, pos));
}

int
list_insert (List *list, const size_t pos, const void *item)
{
  ListNode *cur;
  
  assert (list != NULL);
  
  /* Standard failure cases:
     1 - If the pos is larger than the list, we won't insert it in the list.
     2 - If the pos is less than 0, it's not going to be in this list.
  */
  if (pos > list_size (list) || pos < 0)
    return 0;

  /* Insertion at the tail. */
  if (pos == list_size (list))
    return list_insert_helper (list, list->tail, item, 1);
  /* Insertion anywhere else. */
  else
    {
      cur = list_get_helper (list, pos);
      return list_insert_helper (list, cur, item, 0);
    }
}

void 
list_traverser_init (ListTraverser *trav, const List *list)
{
  assert (trav != NULL);
  assert (list != NULL);

  /* Initialize the traverser. */
  trav->list = list;
  trav->last_call = 1;
  trav->cur = NULL;
}

void * 
list_traverser_next (ListTraverser *trav)
{
  /* Help the traverser remember this call. */
  trav->last_call = 1;

  /* If we don't have a cur, we try the first. */
  if (trav->cur == NULL)
    return list_traverser_first (trav);

  /* If we would walk away outside the list, return NULL. */
  if (trav->cur->next == NULL)
    return NULL;

  /* Update and return. */
  trav->cur = trav->cur->next;
  return (void *)trav->cur->item;
}

void * 
list_traverser_prev (ListTraverser *trav)
{
  /* Help the traverser remember this call. */
  trav->last_call = -1;

  /* If we don't have a cur, we try the last. */
  if (trav->cur == NULL)
    return list_traverser_last (trav);

  /* If we would walk away outside the list, return NULL. */
  if (trav->cur->prev == NULL)
    return NULL;

  /* Update and return. */
  trav->cur = trav->cur->prev;
  return (void *)trav->cur->item;
}

void * 
list_traverser_cur (ListTraverser *trav)
{
  /* If we haven't initialized, we won't have a cur. */
  if (trav->cur == NULL)
    return NULL;

  return (void *)trav->cur->item;
}

void *
list_traverser_remove (ListTraverser *trav)
{
  ListNode *del;

  if (trav->cur == NULL)
    return NULL;

  del = trav->cur;

  /* Check to see if we are removing the last item. */
  if (trav->cur->next == NULL || trav->cur->prev == NULL)
    trav->cur = NULL;
  else if (trav->last_call == 1)
    {
      /* Try first to move to the previous, so our next call to 'next' will
	 give the item after the one being removed. */
      if (trav->cur->prev != NULL)
	trav->cur = trav->cur->prev;
      else
	trav->cur = trav->cur->next;
    }
  else
    {
      /* Try first to move to the next, so our next call to 'prev' will
	 give the item before the one being removed. */
      if (trav->cur->next != NULL)
	trav->cur = trav->cur->next;
      else
	trav->cur = trav->cur->prev;
    }

  return list_remove_helper ((List *)trav->list, del);
}

int
list_traverser_insert_before (ListTraverser *trav, const void *item)
{
  return list_insert_helper ((List *)trav->list, trav->cur, item, 0);
}

int
list_traverser_insert_after (ListTraverser *trav, const void *item)
{
  return list_insert_helper ((List *)trav->list, trav->cur, item, 1);
}

void * 
list_traverser_first (ListTraverser *trav)
{
  /* Help the traverser remember this call. */
  trav->last_call = 1;

  /* Move to the head and return it's item. */
  trav->cur = trav->list->head;
  return list_traverser_cur (trav);
}

void * 
list_traverser_last (ListTraverser *trav)
{
  /* Help the traverser remember this call. */
  trav->last_call = -1;

  /* Move to the tail and return it's item. */
  trav->cur = trav->list->tail;
  return list_traverser_cur (trav);
}


/*******************************************************************************
 * Internal Definitions
 ******************************************************************************/
struct list_node * 
list_get_helper (const List *list, size_t pos)
{
  ListNode *cur;
  size_t count, delta;

  assert (list != NULL);

  /* The list could be big. Decide if we'll start at the beginning or end. */
  if (pos > (list_size (list) / 2))
    {
      cur = list->tail;
      count = list_size (list) - 1;
      delta = -1;
    }
  else
    {
      cur = list->head;
      count = 0;
      delta = 1;
    }
  
  /* Loop through the list until we get the the pos. */
  while (count != pos)
    {
      if (delta == 1)
	cur = cur->next;
      else
	cur = cur->prev;

      count += delta;
    }

  return cur;
}

List * 
list_create_helper (ListType type)
{
  List *list;

  /* Allocate space for the new list. */
  list = malloc (sizeof (List));
  if (list == NULL)
    {
      return NULL;
    }

  /* Start off fresh. */
  list->head = NULL;
  list->tail = NULL;
  list->size = 0;
  list->type = type;

  return list;
}
